#include <stdio.h>/* 头文件 */
#include <stdlib.h>
#include <malloc.h>
typedef struct BiTNode
{
char data;
struct BiTNode *lchild,*rchild,*parent;
}
BiTNode,*BiTree;/* 定义结点类型 */
typedef struct QNode
{
BiTree data;
struct QNode *next;
} /* 定义队列的节点类型 */
QNode,*QueuePtr;
typedef struct
{
QueuePtr front;
QueuePtr rear;
}
LinkQueue;/* 队列 */
void InitQueue(LinkQueue *Q)/* 创建队列 */
{
Q->front=Q->rear=(QueuePtr)malloc(sizeof(QNode));
Q->front->next=NULL;
}
void EnQueue(LinkQueue *Q,BiTree e)/* 将元素入队 */
{
QueuePtr p;
p=(QueuePtr)malloc(sizeof(QNode));/* 为结点开辟空间 */
p->data=e;
p->next=NULL;
Q->rear->next=p;
Q->rear=p;
}
BiTree DeQueue(LinkQueue *Q)/* 将元素出列并返回元素的值。 */
{
BiTree e;QueuePtr p;
p=Q->front->next;
e=p->data;
Q->front->next=p->next;
if(Q->rear==p)
Q->rear=Q->front;
free(p);/* 释放节点 */
return (e);

}
int QueueEmpty(LinkQueue *Q)/* 判断队列是否为空 */
{
if(Q->front==Q->rear )
return 1;
else
return 0;
}
BiTree CreateBiTree()/* 创建树 */
{
char p;
BiTree T;
scanf("%c",&p);
if(p==' ')
T=NULL;
else
{
T=(BiTNode *)malloc(sizeof(BiTNode));/* 为结点开辟空间 */
T->parent=NULL;
T->data=p;
T->lchild=CreateBiTree();
T->rchild=CreateBiTree();
}
return (T);
}
BiTree Road(BiTree T,char a)
{
LinkQueue Q;
BiTree p;
InitQueue(&Q);
EnQueue(&Q,T);
while(!QueueEmpty(&Q))
{
p = DeQueue(&Q);
if(p->data==a)
return(p);
if(p->lchild!=NULL)
{
p->lchild->parent=(BiTNode *)malloc(sizeof(BiTNode));
*(p->lchild->parent)=*p;
EnQueue(&Q,p->lchild);
}
if(p->rchild!=NULL)
{
p->rchild->parent=(BiTNode *)malloc(sizeof(BiTNode));
*(p->rchild->parent)=*p;
EnQueue(&Q,p->rchild);
}
}
return(NULL);
}

void main()/* 主函数 */
{
BiTree Ta,p,L;char a;
printf("请创建树：\n");
Ta=CreateBiTree();
getchar();
printf("输入查找的元素");
scanf("%c",&a);
p=Road(Ta,a);
while(p)
{
printf("%c",p->data);
L=p;
p=p->parent;
free(L);
}
}